package com.zjj.algorithm.learning.atguigu.graph;

import java.util.*;

/**
 * 图的示例
 *
 * @author zjj_admin
 * @date 2022/12/4 20:53
 */
public class GraphDemo {

    public static void main(String[] args) {
        Graph graph = new Graph(5);
        graph.addVertex("A");
        graph.addVertex("B");
        graph.addVertex("C");
        graph.addVertex("D");
        graph.addVertex("E");
        graph.addVertex("C");

        graph.addEdge("A", "B", 10);
        graph.addEdge("A", "C", 5);
        graph.addEdge("B", "E", 20);
        graph.addEdge("C", "D", 14);

        int weight = graph.getWeight("C", "D");

        System.out.println("weight = " + weight);

        graph.showGraph();

        graph.updateWeight("A", "C", 66);
        int weight1 = graph.getWeight("A", "C");
        System.out.println("weight1 = " + weight1);
        graph.showGraph();


        boolean existVertex = graph.isExistVertex("A", "B", "P");
        System.out.println("existVertex = " + existVertex);
    }
}


/**
 * 构建一个图，此处使用 邻接表 构建图
 */
class Graph {

    /**
     * 图的顶点，使用 list 存储
     */
    private ArrayList<Vertex> vertexList;

    /**
     * 图的所有的顶点名称
     */
    private ArrayList<String> vertexNames;
    /**
     * 顶点的个数
     */
    private int numOfVertex;

    /**
     * 边的数量
     */
    private int numOfEdges;


    /**
     * 定义一个Map，用于在遍历时是否被访问过
     */
    private Map<String, Boolean> visited;

    private void initializeVisited() {
        for (int i = 0; i < this.vertexNames.size(); i++) {
            this.visited.put(this.vertexNames.get(i), false);
        }
    }


    /**
     * 构建图
     *
     * @param n 图的顶点
     */
    public Graph(int n) {
        vertexList = new ArrayList<>(n);
        vertexNames = new ArrayList<>(n);
        this.numOfVertex = 0;
        this.numOfEdges = 0;
    }

    /**
     * 展示图的状态
     */
    public void showGraph() {
        System.out.println("***********图的状态如下***********");
        System.out.println("顶点数：" + this.numOfVertex);
        System.out.println("边的数量：" + this.numOfEdges);
        System.out.println("所有的顶点有：" + this.vertexList);
        if (this.vertexList.size() > 0) {
            for (Vertex vertex : this.vertexList) {
                vertex.showAdjacentEdge();
                System.out.println();
            }
        }
        System.out.println("************结束*****************");
    }

    /**
     * 深度优先遍历，获取从起始位置到结束位置的所有的路线
     *
     * @param startPoint 起点
     * @param endPoint   终点
     * @return
     */
    public List<Queue<Vertex>> depthFirsTraversal(String startPoint, String endPoint) {
        List<Queue<Vertex>> res = new ArrayList<>();
        Vertex[] vertexs = getVertex(startPoint, endPoint);
        //判断节点是否存在
        if (vertexs[0] == null) {
            throw new NullPointerException(startPoint + " 节点不存在");
        }
        if (vertexs[1] == null) {
            throw new NullPointerException(endPoint + " 节点不存在");
        }
        Vertex startV = vertexs[0];
        Vertex endV = vertexs[1];
        //初始化图都没有被访问
        initializeVisited();
        Queue<Vertex> queue = new ArrayDeque<>();
        //将起始顶点添加到队列中
        queue.add(startV);
        //标注起始顶点为已经访问
        this.visited.put(startPoint, true);
        while (!queue.isEmpty()) {
            //当前节点
            GraphNode curr = queue.peek().firstEdge.next;
            while (curr != null) {
                if (curr.adjvex.equals(endV.name)) {
                    Queue<Vertex> temp = queue;
                    Vertex vertex = new Vertex(curr.adjvex);
                    vertex.firstEdge = curr;
                    vertex.firstEdge.weight = curr.weight;
                    temp.add(vertex);
                    res.add(temp);
                }
                if (this.visited.get(curr.adjvex).equals(false)) {
                    //todo 太难了
                    //将起始顶点的邻接顶点加入队列
                    queue.add(new Vertex(curr.adjvex));
                    //将当前节点标志为已经访问
                    this.visited.put(curr.adjvex, true);
                }

            }
        }


        return null;
    }

    private Vertex[] getVertex(String start, String end) {
        Vertex[] res = new Vertex[2];
        Vertex startV = null;
        Vertex endV = null;
        for (Vertex vertex : this.vertexList) {
            if (vertex.name.equals(start)) {
                startV = vertex;
                continue;
            }
            if (vertex.name.equals(end)) {
                endV = vertex;
            }
            if (startV != null && endV != null) {
                break;
            }
        }
        res[0] = startV;
        res[1] = endV;
        return res;
    }

    /**
     * 给图添加一个顶点
     *
     * @param name
     */
    public void addVertex(String name) {
        //需要先判断图中是否已经存在当前顶点的名称了
        for (Vertex vertex : this.vertexList) {
            if (vertex.name.equals(name)) {
                System.out.println(name + " 顶点已经存在，添加失败");
                return;
            }
        }
        Vertex vertex = new Vertex(name);
        this.vertexList.add(vertex);
        this.vertexNames.add(name);
        this.numOfVertex++;
    }

    /**
     * 判断顶点是否存在
     *
     * @param vertex 需要判断的顶点名称
     * @return
     */
    public boolean isExistVertex(String... vertex) {
        for (String name : vertex) {
            if (!this.vertexNames.contains(name)) {
                return false;
            }
        }
        return true;
    }

    /**
     * 为图添加一条边
     *
     * @param start  边的起始节点
     * @param end    边的终止节点
     * @param weight 边的权重
     */
    public boolean addEdge(String start, String end, int weight) {
        //找到当前这条边起始节点所在的
        Vertex[] vertexs = getVertex(start, end);
        Vertex startV = vertexs[0];
        Vertex endV = vertexs[1];
        //判断节点是否存在
        if (startV == null) {
            throw new NullPointerException(start + " 节点不存在");
        }
        if (endV == null) {
            throw new NullPointerException(end + " 节点不存在");
        }
        //采用头插法插入领边节点
        GraphNode startNode = new GraphNode(start, weight);
        GraphNode endNode = new GraphNode(end, weight);

        boolean isAdd = addEdge(startV, endNode);
        addEdge(endV, startNode);

        if (isAdd) {
            //将边的数量 + 1
            this.numOfEdges++;
            return true;
        }
        return false;
    }


    /**
     * 修改图边的权重
     *
     * @param start
     * @param end
     * @param weight
     */
    public boolean updateWeight(String start, String end, int weight) {
        Vertex[] vertexs = getVertex(start, end);
        Vertex startV = vertexs[0];
        Vertex endV = vertexs[1];
        //判断节点是否存在
        if (startV == null) {
            throw new NullPointerException(start + " 节点不存在");
        }
        if (endV == null) {
            throw new NullPointerException(end + " 节点不存在");
        }
        GraphNode startNode = new GraphNode(start, weight);
        GraphNode endNode = new GraphNode(end, weight);
        boolean updateWeight = updateWeight(startV, endNode);
        if (updateWeight) {
            updateWeight(endV, startNode);
            return true;
        }
        return false;

    }

    /**
     * 修改权值
     *
     * @param vertex
     * @param graphNode
     * @return
     */
    private boolean updateWeight(Vertex vertex, GraphNode graphNode) {
        GraphNode firstEdge = vertex.firstEdge;
        if (firstEdge.next == null) {
            return false;
        }
        //定义当前指针，让其指向第一个邻节点
        GraphNode curr = firstEdge.next;
        while (true) {
            if (curr.adjvex.equals(graphNode.adjvex)) {
                curr.weight = graphNode.weight;
                return true;
            }
            if (curr.next == null) {
                return false;
            }
            curr = curr.next;
        }
    }


    /**
     * 获取两个顶点之间的权重
     *
     * @param start
     * @param end
     * @return
     */
    public int getWeight(String start, String end) {
        Vertex startV = null;
        for (Vertex vertex : this.vertexList) {
            if (vertex.name.equals(start)) {
                startV = vertex;
                break;
            }
        }
        if (startV == null) {
            throw new NullPointerException(start + " 顶点不存在");
        }
        GraphNode firstEdge = startV.firstEdge;
        GraphNode curr = firstEdge.next;
        if (curr == null) {
            //当返回 -1 时表示者两个顶点之间没有边
            return -1;
        }
        while (true) {
            if (curr.adjvex.equals(end)) {
                return curr.weight;
            }
            if (curr.next == null) {
                return -1;
            }
            curr = curr.next;
        }
    }

    /**
     * 为顶点添加领边，当边已经存在时，就不添加了，权值不同就修改成最新的权值
     *
     * @param vertex
     * @param graphNode
     */
    private boolean addEdge(Vertex vertex, GraphNode graphNode) {
        GraphNode firstEdge = vertex.firstEdge;
        if (firstEdge.next == null) {
            firstEdge.next = graphNode;
            return true;
        }
        //定义当前指针，让其指向第一个邻节点
        GraphNode curr = firstEdge.next;
        //依次遍历，使用尾插法插入
        while (true) {
            if (curr.adjvex.equals(graphNode.adjvex)) {
                return false;
            }
            if (curr.next == null) {
                curr.next = graphNode;
                return true;
            }
            curr = curr.next;
        }
    }

}

/**
 * 图的顶点
 */
class Vertex {
    /**
     * 顶点的名称
     */
    String name;
    /**
     * 顶点的索引
     */
    GraphNode firstEdge;

    public Vertex(String name) {
        this.name = name;
        firstEdge = new GraphNode(null, 0);
    }

    @Override
    public String toString() {
        return name;
    }

    public void showAdjacentEdge() {
        GraphNode curr = this.firstEdge.next;
        System.out.print(this.name + " 的邻接节点有：");
        while (curr != null) {
            System.out.print("->" + curr.adjvex + ":" + curr.weight);
            curr = curr.next;
        }
    }
}

class GraphNode {
    /**
     *
     */
    String adjvex;
    /**
     * 两个顶点之间的权重
     */
    int weight;
    /**
     * 下一个相连的边
     */
    GraphNode next;

    public GraphNode(String adjvex, int weight) {
        this.adjvex = adjvex;
        this.weight = weight;
    }
}
